package io.zouyalong.algo.leetcode;

import java.util.HashMap;

/**
 * https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 */
public class LongestSubstringWithoutRepeatingCharacters {
    public static void main(String[] args) {
        var src = new String("auvaldkfhijk1j123k21knbvnakdfakfnad;fji23423kanvidnnalxld");
//        var src = "testsafsdeuyobvt";
        var inst = new LongestSubstringWithoutRepeatingCharacters();
        System.out.printf("string(%d): `%s`\n", src.length(), src);
        var start = System.currentTimeMillis();
        var len = inst.solution1Dp(src);
        System.out.printf("\tdp(%dms): %d\n", System.currentTimeMillis() - start, len);
        start = System.currentTimeMillis();
        len = inst.solution2SlideWindow(src);
        System.out.printf("\tsolution2SlideWindow(%dms): %d\n", System.currentTimeMillis() - start, len);
    }

    public int solution1Dp(String src) {
        var size = src.length();
        if (size == 0) {
            return 0;
        }
        var chars = src.toCharArray();
        var uniqueLength = new int[size];
        uniqueLength[0] = 1;
        var trailingChars = new HashMap<Character, Boolean>();
        trailingChars.put(chars[0], true);
        for (int i = 1; i < size; i++) {
            var currentChar = chars[i];
            if (trailingChars.putIfAbsent(currentChar, true) != null) {
                // not null && true, 字符已经出现了
                uniqueLength[i] = uniqueLength[i-1];
                trailingChars.clear();
                for (int j = i; j>= 0; j--) {
                    System.out.printf("put char(%s), current(%s)\n", chars[j], trailingChars);
                    if (trailingChars.putIfAbsent(chars[j], true) != null) {
                        System.out.printf("after put char(%s), current(%s)\n", chars[j], trailingChars);
                        break;
                    }
                }
            } else {
                System.out.printf("current(i=%d), trainChars(%s)\n", i, trailingChars.toString());
                uniqueLength[i] = Math.max(uniqueLength[i-1], trailingChars.size());
            }
        }
        return uniqueLength[size-1];
    }
    public int solution2SlideWindow(String src) {
        var rightestIndexOfChar = new HashMap<Character, Integer>();
        var chars = src.toCharArray();
        int maxLength = 0;
        int start = 0; // 当前窗口起始位置
        int i = 0;
        for (; i < chars.length; i++) {
            var currentChar = chars[i];
            var lastIndex = rightestIndexOfChar.getOrDefault(currentChar, -1);
            if (lastIndex >= start) {// 在当前窗口内出现了重复字符，结算
                var currentLength = i - start;
                if (currentLength > maxLength) {
                    maxLength = currentLength;
                }
                start = lastIndex + 1;
            }
            rightestIndexOfChar.put(currentChar, i);
        }
        return Math.max(i-start, maxLength);
//        return maxLength;
    }
}
